package org.example.myleet.p1200;

import java.util.*;

public class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        List<List<Integer>> result = new ArrayList<>(arr.length / 2);
//        Arrays.sort(arr);
        arr = selectSort(arr);
        int minDiff = arr[1] - arr[0], diff;
        result.add(getPair(arr[0], arr[1]));
        int i = 2;
        while (i < arr.length) {
            diff = arr[i] - arr[i - 1];
            if (diff == minDiff) {
                result.add(getPair(arr[i - 1], arr[i]));
            } else if (diff < minDiff) {
                minDiff = diff;
                result.clear();
                result.add(getPair(arr[i - 1], arr[i]));
            }
            ++i;
        }
        return result;
    }

    private int[] selectSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, Math.abs(num));
        }
        int[] numCount = new int[2 * max + 1];
        for (int num : arr) {
            ++numCount[num + max];
        }
        int[] sortedArr = new int[arr.length];
        int num = -max, i = 0;
        while (num <= max) {
            int idx = num + max;
            int count = numCount[idx];
            if (0 == count) {
                ++num;
                continue;
            }
            sortedArr[i++] = num;
            --numCount[idx];
        }
        return sortedArr;
    }

    private List<Integer> getPair(int num1, int num2) {
        List<Integer> pair = new ArrayList<>(2);
        pair.add(num1);
        pair.add(num2);
        return pair;
    }
}
